import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Test {
    public static void main(String[] args) {
        String s = "wordgoodgoodgoodbestword";
        String[] words = {"word","good","best","good"};//s.split(" ");
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        list = solution.findSubstring(s,words);
        for(Integer i : list){
            System.out.println(i);
        }
    }
}

class Solution {
    //自己写完第一个，听完老师的，再来一遍
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();

        Map<String,Integer> map1 = new HashMap<>();
        for (String word : words) {
            map1.put(word,map1.getOrDefault(word,0)+1);
        }

        int len = words[0].length(),m = words.length;
        for(int i = 0;i<len;i++){
            //这里又忘了
            Map<String, Integer> map2 = new HashMap<>();
            int count = 0;
            for(int left=i,right=i;right+len<=s.length();right+=len){
                //进窗口+维护count
                String in = s.substring(right,right+len);
                map2.put(in,map2.getOrDefault(in,0)+1);
                    //维护count
                if(map1.getOrDefault(in,0)>=map2.get(in)){
                    count++;
                }

                //判断+维护count
                if(right-left+1>m*len){
                    //出窗口
                    String out = s.substring(left,left+len);
                    if(map2.get(out)<=map1.getOrDefault(out,0)){
                        count--;
                    }
                    map2.put(out,map2.get(out)-1);
                    left+=len;
                }


                //更新结果
                if(count==m){
                    list.add(left);
                }
            }
        }
        return list;


    }

    public List<Integer> findSubstring1(String s, String[] words) {
        //
        List<Integer> res = new ArrayList<Integer>();
        int left = 0,right = 0;
        int count = 0;//窗口中有效串的个数
        int len = words[0].length();//注意，这不是words数组的长度。
        Map<String,Integer> map1 = new HashMap<>();
        Map<String,Integer> map2 = new HashMap<>();
        for(String str : words){
            map1.put(str,map1.getOrDefault(str,0)+1);
            //map1.put(str,getOrDefault(str,0)+1);——这种方法：即使idea弹出来了，也自己再理解着絮叨着敲一遍，强化一下
        }


        //细节一：需要使用到len次滑动窗口（思路打开，不要局限——只能用一次滑动窗口）
        for(int i = 0 ; i < len ; i++){
            for(left=i,right=i;right<=s.length()-len;right+=len){//每次使用滑动窗口//细节二：每次移动是3

                //进窗口
                String in =  s.substring(right,right+len);//截取字符串，两个参数都是下标，要合法，并且左闭右开
                map2.put(in,map2.getOrDefault(in,0)+1);
                    //维护count
                if(map1.containsKey(in)){
                    if(map1.get(in)>=map2.get(in)){
                        count++;
                    }
                }

                //判断
                int width = right+len-1 - left + 1;

                if(width>(len*words.length)){
                    //出窗口
                    String out = s.substring(left,left+len);
                    if(map1.containsKey(out)&&map1.get(out)>=map2.get(out)){
                        count--;
                    }
                    map2.put(out,map2.get(out)-1);
                    left+=len;
                }

                //更新结果
                if(count == words.length){
                    if(!res.contains(left)) res.add(left);
                }


            }
            map2.clear();//细节：记得清表！！！（可以观察出问题的案例：都是非第一次使用滑动窗口的），另外，left也要同步清
            count=0;//这里也是写；记得清零
        }
        return res;
    }
}
